package net.jcip.examples.chapter8;

import java.util.*;
import java.util.concurrent.*;

/**
 * TransformingSequential
 * <p/>
 * Transforming sequential execution into parallel execution
 *
 * @author Brian Goetz and Tim Peierls
 */

/**
 * ConcurrentLinkedQueue 是 Java 中的一个线程安全的非阻塞队列，它实现了 Queue 接口，适用于多线程环境下的高并发场景。
 *
 * 主要特性和用途：
 *
 * 	1.	线程安全：
 * 	•	ConcurrentLinkedQueue 是线程安全的，支持多线程并发操作，无需显式的同步措施（如锁）。
 * 	•	它通过使用一些技术（如 CAS 操作）来确保线程安全，从而避免了在队列操作时的竞态条件和死锁。
 * 	2.	基于链表：
 * 	•	内部实现是基于链表的数据结构，因此在并发情况下，操作效率比基于数组的队列（如 ArrayBlockingQueue）更高。
 * 	•	链表结构使得在高并发的情况下，对队列的插入和移除操作具有较好的性能表现。
 * 	3.	无界队列：
 * 	•	ConcurrentLinkedQueue 是无界队列，它不会对队列中元素的数量进行限制。这意味着你可以不受限制地向队列中添加元素。
 * 	4.	适用场景：
 * 	•	适合于生产者-消费者模型，多个生产者线程可以同时向队列中添加元素，多个消费者线程可以同时从队列中取出元素，而无需额外的同步。
 * 	•	当你需要在多线程环境下使用一个高效的、非阻塞的先进先出（FIFO）队列时，ConcurrentLinkedQueue 是一个很好的选择。
 *
 *
 * 	基本操作：
 * 	使用 add 或 offer 方法将元素添加到队列的末尾
 * 	使用 peek 方法获取但不移除队列的头元素，如果队列为空则返回 null：
 * 	使用 poll 方法从队列中移除并返回队列的头元素，如果队列为空则返回 null：
 * 	使用 isEmpty 方法判断队列是否为空：
 * 	使用 size 方法获取队列中元素的个数，注意这个方法的结果只是一个估计值，在多线程环境下可能不是实时的：
 *
 *
 */
public abstract class TransformingSequential {

    void processSequentially(List<Element> elements) {
        for (Element e : elements)
            process(e);
    }

    void processInParallel(Executor exec, List<Element> elements) {
        for (final Element e : elements)
            exec.execute(() -> process(e));
    }

    public abstract void process(Element e);


    public <T> void sequentialRecursive(List<Node<T>> nodes, Collection<T> results) {
        for (Node<T> n : nodes) {
            results.add(n.compute());
            sequentialRecursive(n.getChildren(), results);
        }
    }

    public <T> void parallelRecursive(final Executor exec,
                                      List<Node<T>> nodes,
                                      final Collection<T> results) {
        for (final Node<T> n : nodes) {
            exec.execute(() -> results.add(n.compute()));
            parallelRecursive(exec, n.getChildren(), results);
        }
    }

    public <T> Collection<T> getParallelResults(List<Node<T>> nodes)
            throws InterruptedException {
        ExecutorService exec = Executors.newCachedThreadPool();
        Queue<T> resultQueue = new ConcurrentLinkedQueue<T>();
        parallelRecursive(exec, nodes, resultQueue);
        exec.shutdown();
        exec.awaitTermination(Long.MAX_VALUE, TimeUnit.SECONDS);
        return resultQueue;
    }

    interface Element {
    }

    interface Node <T> {
        T compute();

        List<Node<T>> getChildren();
    }
}

